О НИЖНЕЙ ОЦЕНКЕ ФУНКЦИИ ШЕННОНА ДЛИНЫ СЕРТИФИКАТА ПОВТОРНОСТИ
БУЛЕВЫХ ФУНКЦИЙ В ОДНОМ СЕМЕЙСТВЕ БАЗИCОВ 

Кафтан Дарья Владимировна, аспирант, Московский государственный университет имени М. В. Ломоносова (Россия, г. Москва, Ленинские горы, 1), blond.programmist@gmail.com

517.718.7

Актуальность и цели. В связи с развитием информатики и цифровой техники актуальным является исследование различных свойств булевых функций. Одним из важных свойств является возможность представления функции в заданном базисе формулой без повторения переменных (бесповторной формулой). Функции, которые можно так представить (бесповторные функции в данном базисе), можно рассматривать как класс «простых» функций в данном базисе. В статье рассматривается следующая задача: для заданной функции требуется найти такой набор строк (сертификат), с помощью которого можно проверить ее повторность в предэлементарном базисе, содержащем функцию семейства дискриминаторных, зависящую от s переменных. Целью данной работы является улучшение нижней оценки функции Шеннона длины сертификата повторности в этом базисе.
Материалы и методы. Используется метод разнозначных матриц и удачный подбор функции с высокой нижней оценкой длины сертификата повторности.
Результаты и выводы. Показано, что сертификат повторности функции n переменных, равной единице только на нулевом и единичном наборах, в этом базисе имеет длину не менее n/2 – s + 1. Таким образом улучшена известная нижняя оценка n/s функции Шеннона длины сертификата повторности в этом базисе.

бесповторная функция, сертификат повторности, семейство дискриминаторных функций, разнозначная матрица.

1. Shannon, C. E. A symbolic analysis of relay and switching circuits / C. E. Shannon // Trans. – 1938. – AIEE 57. – P. 713–723.
2. Стеценко, В. А. О предплохих базисах в / В. А. Стеценко // Математические вопросы кибернетики. – Вып. 4. – М. : Физматлит, 1992. – С. 139–177.
3. Chistikov, D. Certificates of Non-Membership for Classes of Read-Once Functions / D. Chistikov, V. Fedorova, A. Voronenko // Fundamenta Informaticae. – 2014. – № 132 (1). – P. 63–77.
4. Вороненко, А. А. Повторность булевых функций в элементарном базисе / А. А. Вороненко, В. С. Федорова, Д. В. Чистиков // Известия вузов. Математика. – 2011. – № 11. – C. 72–77.
5. Вороненко, А. А. О функции Шеннона для длины сертификата повторности булевых функций в одном семействе базисов / А. А. Вороненко // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. – 2013. – № 4. – С. 45–47.
6. Вороненко, А. А. О сложности доказательства повторности булевых функций в бинарном базисе / А. А. Вороненко // Прикладная дискретная математика. – 2011. – № 3 (13). – С. 12–16.